As one of data compression encoding techniques, PackBits encoding is known. PackBits encoding is one of runlength encoding techniques, and can decode information before encoding without any losses, i.e., it is also lossless encoding.
PackBits encoding will be explained below under the assumption that one data as a unit to be encoded consists of 8 bits (data is, e.g., 8-bit multi-valued pixel data). Also, data before encoding will be referred to as raw data, and a stream of raw data before encoding will be referred to as a raw data stream.
PackBits encoding separates a raw data stream into “continuous parts of the same data” and “continuous parts of different data”, and appends “length information” of data to each part. Each “continuous part of the same data” is expressed by a pattern “runlength+data”, and each “continuous part of different data” is expressed by a pattern “runlength of different data+different data stream”. A data stream generated by this process is output as PackBits encoded data.
Assume that a raw data stream (24 data) expressed by:0,0,0,0,1,2,3,4,4,4,4,4,4,4,4,5,5,6,7,8,8,9,10,10  (1)is input. Each individual data is expressed by 8 bits (data ranging from 0 to 255).
In this case, this raw data stream is separated into “continuous parts of the same data” and “continuous parts of different data like:                0,0,0,0,        1,2,3,        4,4,4,4,4,4,4,4,        5,5,        6,7,        8,8,        9,        10,10“Length information” is appended to each part, and in each “part wherein the same data continuously appear”, a data part is compressed to only one data.0,0,0,0,(−4),0,1,2,3,(3),1,2,3,4,4,4,4,4,4,4,4,(−8),4, 5,5,(−2),5,6,7,(2),6,7,8,8,(−2),89,(1),910,10(−2),10  (3)        
In (3), “length information” is put in parentheses. The positive and negative signs of “length information” are attached to discriminate whether the same data or different data continuously appear. That is, the negative sign indicates “continuous parts of the same data” and the positive sign indicates “continuous parts of different data”. This “length information” is embedded in a data stream as “length code data” having the same 8-bit width, and the data stream is output. More specifically, the most significant bit MSB of 8 bits of the length code data is handled as a positive/negative sign bit.
Only one data like the value “9”, which is present in isolation between continuous data, is defined as “run of one different data”. For this reason, a minimum runlength of same data is 2.
The relationship (table) among the length code data, “runlength of data with the same value”, and “runlength of data with different values” are as follows (note: “0x” indicates a hexadecimal number).
Runlength of data with thedifferent valueLength code data 10x00 20x01 30x00::1270x7E1280x7F
Runlength of data withsame valuesLength code data 2 (−2) 0xFF 3 (−3) 0xFE::127 (−127)0x82128 (−128)0x81
Therefore, when raw data stream (1) above is PackBits-encoded, an encoded data stream expressed by:FD,00,02,01,02,03,F9,04,FF,5,01,06,07,FF,08,00,09,FF,10  (4)is generated.
As described above, PackBits encoding can express a runlength of the different data from 1 to 128, and a runlength of same data from 2 to 128. Therefore, if the runlength of the same data is 129 or more, a code of a run of 128 data (length code data+data that run) is generated, and for the 129th and subsequent data, a code having that 129th data as a start point is generated. The same applies to a run of different data.
Note that PackBits encoding does not generate 0x80 as “length code data”, as shown in the table above. Therefore, this “0x80” is often defined as end-of-list code data indicating the end of an encoded data stream.
In the following description, “length code data” in PackBits encoded data will be expressed by “length information” and a part indicating an actual data value or values output after the length information will be expressed by “data part”.
As described above, PackBits encoding can reduce the data size after encoding as the frequency of occurrence of runs of data with the same values increases (to attain a high compression ratio).
In general, upon compressing data, compression encoding is often made while setting a target size like ½ or less (compression ratio of twice or more) or ¼ or less (compression ratio of four times or more) with respect to a raw data size. In case of PackBits encoding, the compression ratio is improved when three or more data run. However, when different data run, the data size increases in correspondence with “length information” appended.
Therefore, when a target data size cannot be attained by PackBits encoding, it cannot be attained unless a change is made to form runs of the same data.
If an arbitrary bit of raw data is fixed to zero, the number of types of values that can be assumed is halved, and the same values become more likely to run inevitably. Hence, upon compressing such data, a high compression ratio is obtained. For example, taking a multi-valued pixel as an object to be compression-encoded, if its LSB is fixed to zero, both pixel values expressed by 2n and 2n+1 (n=0, 1, 2, . . . ) are rounded to “2n”. In case of a halftone image, since neighboring pixels have small density and luminance differences, the same values are easily obtained by changing the bit values, as described above. That is, as can be seen from the above description, a high compression ratio can be attained by executing the bit change process. Likewise, when two appropriate bits are fixed to zero, a still higher compression ratio can be attained.
However, in order to execute the aforementioned rounding process for each individual data of a set of original raw data (e.g., of multi-valued image data), processes proportional to the data size are required, and a high processing speed cannot be expected. Also, a memory that stores whole original raw data is required to attain such process.